#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N=3*1e5+10;
int f[N];
int mn[N];
struct node{
    int x,y,z;
    bool operator<(const struct node& p1) const
    {
        return z<p1.z;
    }
    
};
int Find(int x)
{
    if(f[x]!=x)
    {
        f[x]=Find(f[x]);
    }
    return f[x];
}
void Union(int x,int y,int z)
{
	x=Find(x);
	y=Find(y);
	f[x]=y;
	mn[y]=min(mn[y],mn[x]);
	mn[y]=min(mn[y],z);
}
void solve()
{
    int n,m;
    cin>>n>>m;
    int ret=0x3f3f3f3f;
    memset(mn,0x3f3f3f3f,sizeof(mn));
    for(int i=0;i<=n;i++)
        f[i]=i;
    vector<node> v;
    for(int i=0;i<m;i++)
	{
        node t;
        scanf("%d%d%d",&t.x,&t.y,&t.z);
        v.push_back(t);
	}
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        Union(v[i].x,v[i].y,v[i].z);
        if(Find(1)==Find(n))
        {
			ret=min(ret,mn[Find(1)]+v[i].z);
		}
    }
    if(Find(1)!=Find(n))
    {
		cout<<-1<<endl;
	}
	else{
		cout<<ret<<endl;
	}

}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();  
    }
    return 0;
}
